package com.dollama.random.utils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
 * Created by tony on 2017/5/10.
 */

public class SortUtil {
    /**
     * 直接插入排序
     * */
    public static ArrayList insertSort(ArrayList arrayList,CompareListener compareListener){
        Object temp;
        for (int i = 1; i < arrayList.size(); i++) {
            temp = arrayList.get(i);
            if (compareListener.compare(arrayList.get(0),arrayList.get(i))) {
                arrayList.remove(i);
                arrayList.add(0,temp);
            } else if (!compareListener.compare(arrayList.get(i-1),arrayList.get(i))) {
            } else {
                for (int j = 0; j < i; j++) {
                    //其实并不需要 j<x<j+1，因为是升序，所以遇到第一个比自己大就可以插入了
                    if (!compareListener.compare(arrayList.get(j),arrayList.get(i))
                            &&(j+1)<i&&compareListener.compare(arrayList.get(j+1),arrayList.get(i))) {
                        arrayList.remove(i);
                        arrayList.add(j+1,temp);
                        break;
                    }
                }
            }
        }
        return arrayList;
    }

    //希尔排序//变形的插入排序
    //不断缩小步长，对原数组进行分组，排序
    public static ArrayList shellSort (ArrayList arrayList,CompareListener compareListener) {
        int gap = arrayList.size(),i,j,k,n;
        Object temp;
        for (gap = gap/2;gap>0;gap/=2) {
            for (i=0;i<gap;i++) {
                for (j = i+gap ;j<arrayList.size();j+=gap) {
                    for (n=i;n<j;n+=gap) {
                        if (!compareListener.compare(arrayList.get(j),arrayList.get(n))){
                            temp = arrayList.get(j);
                            k = j-gap;
                            while (k>=0&& compareListener.compare(arrayList.get(k),temp)){
                                arrayList.set(k+gap,arrayList.get(k));
                                k-=gap;
                            }
                            arrayList.set(n,temp);
                        }
                    }
                }
            }
        }
        return arrayList;
    }

    //简单排序
    //按照索引位置进行，每次找到当前最小，放到对应位置
    public static ArrayList simpleSort (ArrayList arrayList,CompareListener compareListener) {
        Object min,temp;
        int i,j,k = 0;
        for (i = 0;i<arrayList.size()-1;i++) {
            temp = arrayList.get(i);
            min = arrayList.get(i);
            for (j = i+1 ;j<arrayList.size();j++) {
                if (compareListener.compare(min,arrayList.get(j))) {
                    min = arrayList.get(j);
                    k = j;
                }
            }
            arrayList.set(i,min);
            arrayList.set(k,temp);
        }
        return arrayList;
    }

    //堆排序
    /**
     * 利用堆的特性（小顶堆）
     * 左右两叶子节点都需要大于根节点，即如果新插入的叶子节点小于根节点 则新插入的节点的兄弟节点必然大于这个新插入的节点
     * 所以可以直接将这个新加入的节点与跟节点交换，得到新的二叉树，直到这个新节点不再能上升为新的根节点，则这个树回复成小顶堆
     *
     * 这是只需要将排序操作转化成两个动作
     * 1.生成小顶堆
     * 2.抽取根节点
     * 3.再次形成小顶堆
     * */
    public static ArrayList heapSort (ArrayList arrayList,CompareListener compareListener) {
        ArrayList arrayList1 = new ArrayList();
        for (int i=0;i<arrayList.size();i++) {
            insertHeap(arrayList1,arrayList.get(i),compareListener);
        }
        return getHeapList(arrayList1,compareListener);
    }

    private static void insertHeap(ArrayList arrayList,Object object,CompareListener compareListener){
        arrayList.add(object);
        int lastIndex = arrayList.size()-1,fatherIndex,k;
        k = lastIndex;
        fatherIndex = (k-1)/2;

        while (fatherIndex>=0&&k!=0){
            /**
             * 如果根节点大于当前操作节点 则交换
             * */
            if (!compareListener.compare(arrayList.get(fatherIndex),object)) {
                break;
            }
            arrayList.set(k,arrayList.get(fatherIndex));
            k = fatherIndex;
            fatherIndex = (k-1)/2;
        }
        arrayList.set(k,object);
    }
    private static ArrayList getHeapList (ArrayList arrayList,CompareListener compareListener) {
        ArrayList arrayList2 = new ArrayList();
        ArrayList arrayList3 = new ArrayList();
        ArrayList remainder = arrayList;
        while (remainder.size()!=0){
            arrayList2.add(remainder.get(0));
            remainder.remove(0);
            arrayList3.clear();
            for (int w = 0;w<remainder.size();w++) {
                insertHeap(arrayList3,arrayList.get(w),compareListener);
            }
            remainder.clear();
            remainder.addAll(arrayList3);
        }
        return arrayList2;
    }

    //冒泡排序
    public static ArrayList bubbleSort (ArrayList arrayList,CompareListener compareListener) {
        Object temp;
        for (int j = arrayList.size()-1;j >0;j--) {
            for (int i = 0;i<j;i++) {
                if (compareListener.compare(arrayList.get(i),arrayList.get(i+1))) {
                    temp = arrayList.get(i);
                    arrayList.set(i,arrayList.get(i+1));
                    arrayList.set(i+1,temp);
                }
            }
        }
        return arrayList;
    }

    //快速排序
    //取任意基数，把比他小的放左边，比他大的放右边，递归，不断对生成的左右两边进行快速排序
    public static ArrayList quickSort (ArrayList arrayList,CompareListener compareListener) {
        quickSort1(arrayList,compareListener,0,arrayList.size()-1);
        return arrayList;
    }

    private static void quickSort1 (ArrayList arrayList,CompareListener compareListener,int left,int right) {
        Object temp = arrayList.get(left),t;
        if (left>right) {
            return;
        }
        int i = left,j=right;
        while (i!=j){
            while (!compareListener.compare(temp,arrayList.get(j))&&i<j)
                j--;
            while (!compareListener.compare(arrayList.get(i),temp)&&i<j)
                i++;
            if (i<j) {
                t = arrayList.get(i);
                arrayList.set(i,arrayList.get(j));
                arrayList.set(j,t);
            }
        }
        arrayList.set(left,arrayList.get(i));
        arrayList.set(i,temp);

        if(i>0&&left<10&&left<(i-1))
        quickSort1(arrayList,compareListener,left,i-1);
        if (i<8&&right>0&&right>i+1)
        quickSort1(arrayList,compareListener,i+1,right);
    }

    //递归排序
    //把数组分成两半，直到不可分，对每一组进行排序
    public static ArrayList recursionSort (ArrayList arrayList,CompareListener compareListener) {
        doRecursionSort(arrayList,0,arrayList.size()-1,compareListener);
        return arrayList;
    }

    private static void doRecursionSort(ArrayList arrayList,int first,int last,CompareListener compareListener) {
        if (first>=last) {
            return;
        }

        int middle = (first+last)/2;
        if (middle-first>=1) {
            doRecursionSort(arrayList,first,middle,compareListener);

        }
        if (last-middle>=1) {
            doRecursionSort(arrayList,middle+1,last,compareListener);
        }
        mergSortList(arrayList,first,middle,last,compareListener);
    }
    private static void mergSortList (ArrayList arrayList,int first,int middle,int last,CompareListener compareListener) {
        int i = first,j = middle+1,k = 0;
        ArrayList tempList = new ArrayList();
        if (last-first == 1) {
            if (compareListener.compare(arrayList.get(i),arrayList.get(j))) {
                tempList.add(arrayList.get(j));
                tempList.add(arrayList.get(i));
            }else {
                tempList.add(arrayList.get(i));
                tempList.add(arrayList.get(j));
            }
        }  else if (last-first == 0) {
            tempList.add(arrayList.get(i));
        }else {
            while(i<(middle+1)||j<(last+1)) {
                if (i==middle+1) {
                    tempList.add(arrayList.get(j));
                    j++;
                } else if(j==last+1) {
                    tempList.add(arrayList.get(i));
                    i++;
                } else if (compareListener.compare(arrayList.get(i),arrayList.get(j))) {
                    tempList.add(arrayList.get(j));
                    j++;
                }else {
                    tempList.add(arrayList.get(i));
                    i++;
                }
            }
        }

        int n = 0;
        for (int m = first;m<=last;m++) {
            arrayList.set(m,tempList.get(n));
            n++;
        }
    }
    //基数排序
    //对不同数位的数字进行比较形成顺序
    public static ArrayList radixSort (ArrayList<Integer> arrayList,CompareListener compareListener) {
        //只能对纯数字进行排序
        int maxIndex = 0;
        int max = arrayList.get(0);
        for (int i=1;i<arrayList.size();i++) {
            if (arrayList.get(i)>max) {
                maxIndex = i;
                max = arrayList.get(i);
            }
        }
        int digit = getDigit(max);
        int baseNumber =1,remainder,remainder1;
        Map<Integer,ArrayList<Integer>> map = new HashMap<>();
        ArrayList<Integer> resultList = new ArrayList<>();
        for (int j = 0;j<digit+1;j++) {
            map.clear();
            resultList.clear();
            baseNumber = 1;
            for (int w = 0;w<=j;w++) {
                baseNumber = baseNumber*10;
            }
            for (int k = 0;k<arrayList.size();k++) {
                if (arrayList.get(k)*10<baseNumber) {
                    remainder = 0;
                } else {
                    remainder = arrayList.get(k)%baseNumber;
                    if (baseNumber/10>1) {
                        remainder = remainder/(baseNumber/10);
                    }
                }

                if (map.containsKey(remainder)) {
                    map.get(remainder).add(arrayList.get(k));
                } else {
                    ArrayList<Integer> arrayList1 = new ArrayList<>();
                    arrayList1.add(arrayList.get(k));
                    map.put(remainder,arrayList1);
                }
            }
            ArrayList<Integer> arrayList2;
            for (int a = 0;a<10;a++) {
                if (map.containsKey(a)) {
                    arrayList2 = map.get(a);
                    for (int b = 0;b<arrayList2.size();b++){
                        resultList.add(arrayList2.get(b));
                    }
                }
            }
            arrayList.clear();
            arrayList.addAll(resultList);
        }
        return arrayList;
    }

    private static int getDigit(int i){
        int j = i,count=0;
        while (j>10){
            j = j/10;
            count++;
        }
        count++;
        return count;
    }

    public interface CompareListener {
        //true obj1>obj2
        public boolean compare(Object obj1,Object obj2);
    }
}
